import java.util.Arrays;

/**
 * @author 汤奇
 * @version V1.0
 * @Project BookPro
 * @Package PACKAGE_NAME
 * @Description:
 * @Date 2022/7/26 20:17
 */
public class Test07 {
    public static void main(String[] args) {
        int [] a={5,6,8,7,2,9,1,3,4,11,12,10};
        Stack<Integer> arrayStack=new ArrayStack<>();
        for (int i = 0; i < a.length; i++) {
            arrayStack.push(a[i]);
        }
        for (int i = 0; i < a.length; i++) {
            System.out.print(arrayStack.pop()+" ");
        }
        System.out.println(arrayStack.pop());


        Stack<Integer> linkedStack=new LinkedStack<>();
        for (int i = 0; i < a.length; i++) {
            linkedStack.push(a[i]);
        }
        for (int i = 0; i < a.length; i++) {
            System.out.print(linkedStack.pop()+" ");
        }
        System.out.println(linkedStack.pop());
    }

    /**
     * 链表实现栈
     */
    static class LinkedStack<T> implements Stack<T>{
        Node<T> top=null;
        @Override
        public T pop() {
            if(top==null){
                return null;
            }
            if(top.next==null){
                T result=top.value;
                top=null;
                return result;
            }else{
                //头删法
                T result=top.value;
                top=top.next;
                return result;
            }
        }

        @Override
        public void push(T object) {
            if(top==null){
                top=new Node<T>();
                top.value=object;
            }else{
                //准备即将插入的元素节点
                Node p=new Node<T>();
                p.value=object;
                //链表的头插法
                p.next=top;
                top=p;
            }
        }

        class Node<T>{
            T value;
            Node<T> next;
        }
    }


    /**
     * 数组实现栈
     */
    static class ArrayStack<T> implements Stack<T>{
        /**
         * 保存数据的数组
         */
        private Object [] array=null;
        /**
         * 元素的个数
         */
        private int size;
        /**
         * 数组的默认长度
         */
        private static final int DEFAULT_CAPACITY = 10;

        public ArrayStack(){
            array=new Object[DEFAULT_CAPACITY];
            size=0;
        }

        @Override
        public T pop() {
            if(size==0){
                return null;
            }
            T result= (T) array[--size];
            return result;
        }

        @Override
        public void push(T object) {
            if(array.length==size){
                //扩容
                int oldLength=array.length;
                int newLength=oldLength+(oldLength>>1);
                array=Arrays.copyOf(array,newLength);
            }
            array[size++]=object;
        }
    }

    /**
     * 栈的定义
     * @param <T>
     */
    interface Stack<T>{
        /**
         * 出栈的方法
         * @return 栈顶元素
         */
        T pop();

        /**
         * 入栈的方法
         * @param object 待入栈的元素
         */
        void push(T object);
    }
}
